package com.example.demo.lc;

/**
 * @Description TODO
 * @Author wzh
 * @Date 2021/9/22 11:07 上午
 * @Version 1.0
 */
public class Leetcode1140 {
    public static void main(String[] args) {
        int[] piles = {2, 7, 9, 4, 4};
        System.out.println(stoneGameII(piles));
    }

    public static int stoneGameII(int[] piles) {
        int sum = 0;
        //dp[i][j] i是取石子的位置，j是取多少堆 能获取到最大的数量
        int[][] dp = new int[piles.length][piles.length + 1];
        for (int i = piles.length - 1; i >= 0; i--) {
            //后缀之合
            sum += piles[i];
            for (int j = 1; j <= piles.length; j++) {
                //剩下能被全被拿走
                if (i + 2 * j >= piles.length) {
                    dp[i][j] = sum;
                } else {
                    //后缀-另一个人拿到的最大的数量
                    for (int k = 1; k <= 2 * j; k++) {
                        dp[i][j] = Math.max(dp[i][j], sum - dp[i + k][Math.max(j, k)]);
                    }
                }
            }
        }
        return dp[0][1];
    }


    //
    //          [2,7,9,4,4]
    //        j
    //   i          0 	1	2	3	4
    //        1  	10	16	13	8	4
    //        2 	22	24	17	8	4
    //        3 	26	24	17	8	4
    //        4 	26	24	17	8	4
    //        5 	26	24	17	8	4

}
